enum COLOR {
    RED, BLACK
}
public class RedBlackTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public COLOR color = COLOR.RED;//默认为红节点，对冲突敏感，且便于控制黑节点个数
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;
    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            root = node;
            root.color = COLOR.BLACK;//退出前，要将根节点染黑
            return true;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            parent = cur;
            if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            } else {
                return false;
            }
        }
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        node.parent = parent;
        cur = node;
        //调整颜色
        while(parent != null && parent.color == COLOR.RED) {
            TreeNode grand = parent.parent;//parent为红，必有父节点
            if(grand.left == parent) {
                TreeNode uncle = grand.right;
                if(uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grand.color = COLOR.RED;
                    cur = grand;
                    parent = cur.parent;//先迭代一下，如果冲突了，会循环回来
                } else {
                    //uncle不存在 或 uncle为黑色
                    if(cur == parent.right) {
                        rotateLeft(parent);
                        TreeNode temp = cur;
                        cur = parent;
                        parent = temp;
                    }
                    rotateRight(grand);
                    parent.color = COLOR.BLACK;
                    grand.color = COLOR.RED;
                }
            } else {
                //与if完全对称
                TreeNode uncle = grand.left;//改为left
                if(uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grand.color = COLOR.RED;
                    cur = grand;
                    parent = cur.parent;
                } else {
                    if(cur == parent.left) { //改为left
                        rotateRight(parent);//改为右旋
                        TreeNode temp = cur;
                        cur = parent;
                        parent = temp;
                    }
                    rotateLeft(grand);//改为左旋
                    parent.color = COLOR.BLACK;
                    grand.color = COLOR.RED;
                }
            }
        }
        root.color = COLOR.BLACK;//一切结束，统一将根节点染黑
        return true;
    }


    public boolean remove(int val) {
        TreeNode cur = root;
        while(cur != null) {
            if (cur.val > val) {
                cur = cur.left;
            } else if (cur.val < val) {
                cur = cur.right;
            } else {
                removeNode(cur);
                return true;
            }
        }
        return false;
    }
    public void removeNode(TreeNode cur) {
        if(cur.left != null && cur.right != null) {
            //左右均不为空
            TreeNode target = cur.right;
            while(target.left != null) {
                target = target.left;
            }
            cur.val = target.val;
            cur = target;
        }
        TreeNode replacement = cur.left == null ? cur.right : cur.left;
        if(replacement != null) {
            //左右其一为空
            replacement.parent = cur.parent;
            if(cur.parent == null) {
                root = replacement;
            } else if(cur.parent.left == cur) {
                cur.parent.left = replacement;
            } else {
                cur.parent.right = replacement;
            }
            cur.left = cur.right = cur.parent = null;
            if(cur.color == COLOR.BLACK) {
                fixRedBlackTree(replacement);
            }
        } else {
            //左右均为空
            if(cur.parent == null) {
                root = null;
            } else {
                if(cur.color == COLOR.BLACK) {
                    fixRedBlackTree(cur);
                }
                if(cur.parent.left == cur) {
                    cur.parent.left = null;
                } else {
                    cur.parent.right = null;
                }
                cur.parent = null;
            }
        }
    }
    public void fixRedBlackTree(TreeNode cur) {
        while(cur != root && colorOf(cur) == COLOR.BLACK) {
            if(cur == leftOf(parentOf(cur))) {
                TreeNode sib = rightOf(parentOf(cur));
                if(colorOf(sib) == COLOR.RED) {
                    setColor(sib, COLOR.BLACK);
                    setColor(parentOf(cur), COLOR.RED);
                    rotateLeft(parentOf(cur));
                    sib = rightOf(parentOf(cur));
                }
                if(colorOf(leftOf(sib)) == COLOR.BLACK && colorOf(rightOf(sib)) == COLOR.BLACK) {
                    setColor(sib, COLOR.RED);
                    cur = parentOf(cur);
                } else {
                    if(colorOf(rightOf(sib)) == COLOR.BLACK) {
                        setColor(sib, COLOR.RED);
                        setColor(leftOf(sib), COLOR.BLACK);
                        rotateRight(sib);
                        sib = rightOf(parentOf(cur));
                    }
                    setColor(sib, colorOf(parentOf(cur)));
                    setColor(parentOf(cur), COLOR.BLACK);
                    setColor(rightOf(sib), COLOR.BLACK);
                    rotateLeft(parentOf(cur));
                    cur = root;//调整完成
                }
            } else {
                TreeNode sib = leftOf(parentOf(cur));
                if(colorOf(sib) == COLOR.RED) {
                    setColor(sib, COLOR.BLACK);
                    setColor(parentOf(cur), COLOR.RED);
                    rotateRight(parentOf(cur));
                    sib = leftOf(parentOf(cur));
                }
                if(colorOf(leftOf(sib)) == COLOR.BLACK && colorOf(rightOf(sib)) == COLOR.BLACK) {
                    setColor(sib, COLOR.RED);
                    cur = parentOf(cur);
                } else {
                    if (colorOf(leftOf(sib)) == COLOR.BLACK) {
                        setColor(sib, COLOR.RED);
                        setColor(rightOf(sib), COLOR.BLACK);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(cur));
                    }
                    setColor(sib, colorOf(parentOf(cur)));
                    setColor(parentOf(cur), COLOR.BLACK);
                    setColor(leftOf(sib), COLOR.BLACK);
                    rotateRight(parentOf(cur));
                    cur = root;//调整完成
                }
            }
        }
        setColor(cur, COLOR.BLACK);
    }
    public TreeNode parentOf(TreeNode cur) {
        return cur.parent == null ? null : cur.parent;
    }
    public TreeNode leftOf(TreeNode cur) {
        return cur.left == null ? null : cur.left;
    }
    public TreeNode rightOf(TreeNode cur) {
        return cur.right == null ? null : cur.right;
    }
    public COLOR colorOf(TreeNode cur) {
        return cur == null ? COLOR.BLACK : cur.color;
    }
    public void setColor(TreeNode cur, COLOR color) {
        if(cur != null) cur.color = color;
    }


    private void rotateRight(TreeNode parent) {
        TreeNode cur = parent.left;
        TreeNode curRight = cur.right;
        TreeNode parentParent = parent.parent;
        parent.left = curRight;
        if(curRight != null) {
            curRight.parent = parent;
        }
        cur.right = parent;
        parent.parent = cur;
        if(parent == root) {
            root = cur;
            cur.parent = null;
        } else {
            if(parentParent.left == parent) {
                parentParent.left = cur;
            } else {
                parentParent.right = cur;
            }
            cur.parent = parentParent;
        }
    }
    private void rotateLeft(TreeNode parent) {
        TreeNode cur = parent.right;
        TreeNode curLeft = cur.left;
        TreeNode parentParent = parent.parent;
        parent.right = curLeft;
        if(curLeft != null) {
            curLeft.parent = parent;
        }
        cur.left = parent;
        parent.parent = cur;
        if(parent == root) {
            root = cur;
            cur.parent = null;
        } else {
            if(parentParent.left == parent) {
                parentParent.left = cur;
            } else {
                parentParent.right = cur;
            }
            cur.parent = parentParent;
        }
    }


    public void inorder(TreeNode root) {
        if(root == null) return;
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    public boolean isRBTree() {
        if(null == root)
            return true;
        if(root.color != COLOR.BLACK) {
            System.out.println("根节点不为黑");
            return false;
        }
        int blackCount = 0;//任求一条路径中，根节点到叶子节点的黑节点个数，后续路径求得的数目以此为准
        TreeNode cur = root;
        while(null != cur){
            if(cur.color == COLOR.BLACK)
                blackCount++;
            cur = cur.left;
        }
        return _isRBtree(root, 0, blackCount);
    }
    private boolean _isRBtree(TreeNode root, int pathCount, int blackCount) {
        if(null == root) return true;
        if(root.color == COLOR.BLACK) {
            pathCount++;//当前路径中黑节点个数
        }
        TreeNode parent = root.parent;
        if(parent != null && parent.color == COLOR.RED && root.color == COLOR.RED) {
            System.out.println("红节点冲突");
            return false;
        }
        //走到叶子节点，对比pathCount和标准的blackCount
        if(root.left == null && root.right == null && pathCount != blackCount){
            System.out.println("从根节点到叶子节点的路径中，出现了不同数目的黑节点");
            return false;
        }
        return _isRBtree(root.left, pathCount, blackCount) && _isRBtree(root.right, pathCount, blackCount);
    }


    public static void main(String[] args) {
        RedBlackTree redBlackTree = new RedBlackTree();
        //int[] arr = {16, 3, 7, 11, 9, 26, 18, 14, 15};
        int[] arr = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
        for(int i : arr) {
            redBlackTree.insert(i);
        }
        redBlackTree.inorder(redBlackTree.root);
        System.out.println(redBlackTree.isRBTree());

        for(int i : arr) {
            redBlackTree.remove(i);
        }

        redBlackTree.inorder(redBlackTree.root);
        System.out.println(redBlackTree.isRBTree());
    }
}
